<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>Rsa算法 | SmileYi</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="一、介绍1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。 对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找">
<meta name="keywords" content="原创">
<meta property="og:type" content="article">
<meta property="og:title" content="Rsa算法">
<meta property="og:url" content="http://smileyi.gitee.io/2019/04/15/Rsa算法/index.html">
<meta property="og:site_name" content="SmileYi">
<meta property="og:description" content="一、介绍1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。 对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2019-05-03T09:44:55.158Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Rsa算法">
<meta name="twitter:description" content="一、介绍1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。 对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找">
  
    <link rel="alternate" href="/atom.xml" title="SmileYi" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">SmileYi</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/" id="subtitle">只要学会破罐子破摔 世界就会豁然开朗</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">首页</a>
        
          <a class="main-nav-link" href="/archives">归档</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="搜索"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://smileyi.gitee.io"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-Rsa算法" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2019/04/15/Rsa算法/" class="article-date">
  <time datetime="2019-04-15T03:22:19.000Z" itemprop="datePublished">2019-04-15</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/categories/算法/">算法</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      Rsa算法
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h4 id="一、介绍"><a href="#一、介绍" class="headerlink" title="一、介绍"></a>一、介绍</h4><p>1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。</p>
<p>对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。</p>
<h4 id="二、步骤"><a href="#二、步骤" class="headerlink" title="二、步骤"></a>二、步骤</h4><ol>
<li>选取两个互质的整数p和q，互质即p与q的最大公约数为1, 为了方便计算fn，一般直接选取两个质数。</li>
<li>计算p和q的乘积n，n的二进制位数就是密钥长度，一般是1024位，重要场合位2048位</li>
<li>计算n的欧拉函数fn，欧拉函数：即在[1,n)的区间中，与n互质的整数个数。若p、q都为质数，则fn=(p-1)*(q-1)</li>
<li>选取整数e，使得 1 &lt; e &lt; fn 且 e 与 fn 互质</li>
<li>计算e对于fn的模版元素d，即 e * d % fn == 1，根据欧拉定理，整数d一定存在</li>
<li>计算完成，公钥为n和e，私钥为n和d</li>
</ol>
<h4 id="三、加密和解密"><a href="#三、加密和解密" class="headerlink" title="三、加密和解密"></a>三、加密和解密</h4><p>根据上面的步骤，我们获取了公钥n和e和私钥n和d，假设要加密的明文为m，则密文c等于m的e次方除以n的余数：<br><strong>加密：c = m ** e % n</strong><br>要获得的明文m等于c的d次方除以n的余数：<br><strong>解密：m = c ** d % n</strong><br>加密过程用到了n、e，解密的过程用到n、d，至此实现了非对称加密的算法。</p>
<h4 id="四、举例"><a href="#四、举例" class="headerlink" title="四、举例"></a>四、举例</h4><ol>
<li>p = 47; q = 23</li>
<li>n = 47 * 23 = 1081</li>
<li>fn = (47 - 1) * (23 - 1) = 1012</li>
<li>e = 41 // 1 &lt; e &lt; fn &amp;&amp; e 与 fn 互质</li>
<li>d = 469 //模反元素(41 * 469) % 1012 = 1</li>
<li>加密：设明文 m = 16，则密文 c = 16 ** 41 % 1081 = 196</li>
<li>解密：密文 c = 196，则明文 m = 196 ** 469 % 1081 = 16</li>
</ol>
<h4 id="五、安全性"><a href="#五、安全性" class="headerlink" title="五、安全性"></a>五、安全性</h4><p>在密钥的生成步骤中一共出现了6个数字(p q n fn e d)，其中公钥n、e公开，其余四个不需要公开，若要破解，需要根据n和e推导出私钥d：</p>
<ol>
<li>已知ed % fn = 1, 只有知道e和fn才能推导出d</li>
<li>已知fn = (p-1) * (q-1), 只有知道p和q才能推导出fn</li>
<li>n = p * q, 只有将n因数分解才能算出p和q</li>
</ol>
<p>所以如果n被因数分解，d就可以算出，可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。rsa的算法可靠性正是建立在此基础之上。</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://smileyi.gitee.io/2019/04/15/Rsa算法/" data-id="ck5390nrf0010kecz7xa1y0e2" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/原创/">原创</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2019/06/23/Mysql分区/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          Mysql分区
        
      </div>
    </a>
  
  
    <a href="/2019/04/10/Tcp三次握手/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">Tcp三次握手</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">分类</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/Docker/">Docker</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Linux/">Linux</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/MacOS/">MacOS</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Mysql/">Mysql</a><span class="category-list-count">3</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Nginx/">Nginx</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/PHP/">PHP</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Swoole/">Swoole</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/算法/">算法</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/网络/">网络</a><span class="category-list-count">1</span></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">标签</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/原创/">原创</a><span class="tag-list-count">10</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/总结/">总结</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/笔记/">笔记</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/转载/">转载</a><span class="tag-list-count">2</span></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">归档</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/01/">一月 2020</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/07/">七月 2019</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/06/">六月 2019</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/04/">四月 2019</a><span class="archive-list-count">7</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">三月 2019</a><span class="archive-list-count">4</span></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">最新文章</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2020/01/05/Swoole之server/">swoole之server</a>
          </li>
        
          <li>
            <a href="/2020/01/02/Certbot-免费的ssl证书/">Certbot--免费的ssl证书</a>
          </li>
        
          <li>
            <a href="/2019/07/13/Nginx限流配置/">Nginx限流配置</a>
          </li>
        
          <li>
            <a href="/2019/06/23/Mysql分区/">Mysql分区</a>
          </li>
        
          <li>
            <a href="/2019/04/15/Rsa算法/">Rsa算法</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2020 王中艺<br>
      <a href="http://www.beian.miit.gov.cn/">京ICP备18032247号-2</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">首页</a>
  
    <a href="/archives" class="mobile-nav-link">归档</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>